package com.zj.leetcode.medium.hash;

import java.util.*;

/**
 * @program: algorithm
 * @description: 砖墙
 * 554 brick-wall
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class BrickWall {
    public static void main(String[] args) {
//        [[100000000],[100000000],[100000000]]
        List<List<Integer>> wall = new ArrayList<>();
        wall.add(new ArrayList<>(100000000));
        wall.add(new ArrayList<>(100000000));
        wall.add(new ArrayList<>(100000000));

        Solution solution = new BrickWall().new Solution();
        System.out.println(solution.leastBricks(wall));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int leastBricks(List<List<Integer>> wall) {

            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < wall.size(); i++) {
                int num = 0;
                List<Integer> theWall = wall.get(i);
                for (int j = 0; j < theWall.size() - 1; j++) {
                    num += theWall.get(j);
                    map.put(num, map.getOrDefault(num, 0) + 1);
                }
            }

            int max = 0;
            for (Integer value : map.values()) {
                max = Math.max(value, max);
            }
            return wall.size() - max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
